#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pair<int, int>, int> piii;
const int INF = 0x3f3f3f3f;
int chess[110][110];
int ch[110][110];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int g[110][110];
int main()
{
	memset(g, 0x3f, sizeof(g));
	int n, m;
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;
		cin >> chess[x][y];
		chess[x][y] += 1;
	}
	queue<piii> q;
	q.push({ {1,1},chess[1][1] });
	g[1][1] = 0;
	ch[1][1] = chess[1][1];
	while (q.size())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int c = q.front().second;
		q.pop();
		if (x == m && y == m)
		{
			continue;
		}
		if (ch[x][y] != c)
		{
			continue;
		}
		int xx = 0, yy = 0;
		for (int i = 0; i < 4; i++)
		{
			xx = x + dx[i];
			yy = y + dy[i];
			if (xx<1 || xx>m) continue;
			if (yy<1 || yy>m) continue;
			if (chess[x][y] == 0 && chess[xx][yy] == 0) continue;
			if (chess[x][y] == 0)
			{
				if (chess[xx][yy] == c && g[xx][yy] > g[x][y])
				{
					g[xx][yy] = g[x][y];
					q.push({ {xx,yy},chess[x][y] });
					ch[xx][yy] = chess[x][y];
					continue;
				}
				if (chess[xx][yy] != c && g[x][y] + 1 < g[xx][yy])
				{
					g[xx][yy] = g[x][y] + 1;
					q.push({ {xx,yy},chess[x][y] });
					ch[xx][yy] = chess[x][y];
					continue;
				}
			}
			else
			{
				if (chess[x][y] == chess[xx][yy])
				{
					if (g[x][y] < g[xx][yy])
					{
						g[xx][yy] = g[x][y];
						q.push({ {xx,yy},chess[x][y] });
						ch[xx][yy] = chess[x][y];
					}
				}
				else
				{
					if (chess[xx][yy] == 0)
					{
						if (g[xx][yy] > g[x][y] + 2)
						{
							g[xx][yy] = g[x][y] + 2;
							q.push({ {xx,yy},chess[x][y] });
							ch[xx][yy] = chess[x][y];
						}
					}
					else
					{
						if (g[x][y] + 1 < g[xx][yy])
						{
							g[xx][yy] = g[x][y] + 1;
							q.push({ {xx,yy},chess[x][y] });
							ch[xx][yy] = chess[x][y];
						}
					}
				}
			}
		}
	}
	if (g[m][m] == INF)
	{
		cout << -1;
	}
	else
	{
		cout << g[m][m];
	}
	return 0;
}

